Coloration d'un graphe (d'après BAC ES, métropole 2003) - Corrigé

Un petit complément sur les colorations de graphes

On définit le nombre chromatique  $\chi (G)$  d'un graphe $G$ , comme étant le nombre minimal de couleurs à utiliser pour colorier les sommets d'un graphe sans que deux sommets adjacents soient de la même couleur. Par exemple, pour le graphe ci-dessous, le nombre chromatique est 2.

On remarque que le nombre chromatique d'un graphe est toujours inférieur ou égal à  $\Delta (G)+1$ , où  $\Delta (G)$  est le plus grand degré d'un des sommets du graphe  $G$ .

Par ailleurs, pour un graphe complet  $K_n$ , on a  $\chi (K_n)=n=\Delta (K_n)+1$ .

Énoncé

Un concert de solidarité est organisé dans une grande salle de spectacle. À ce concert sont conviés sept artistes de renommée internationale : Luther Allunison (A), John Biaise (B), Phil Colline (C), Bob Ditlâne, Jimi Endisque (E), Robert Fripe (F) et Rory Garaguerre (G).

Les différents musiciens invités refusant de jouer avec certains autres, l'organisateur du concert doit prévoir plusieurs parties de spectacle. Les arêtes du graphe  $G$  ci-dessous indiquent quels sont les musiciens qui refusent de jouer entre eux.

1. Déterminer la matrice d'adjacence du graphe  $G$

2. On considère le sous graphe $G^{\prime }$  de  $G$ , constitué des sommets A, E, F et G.
    a. Que peut-on dire de  $G^{\prime }$ ?
    b. En déduire son nombre chromatique  $\chi (G^{\prime })$ .
    c. Que peut-on en déduire pour  $\chi (G)$  ?

3. Quel est le sommet de plus haut degré de  $G$  ? En déduire un encadrement de  $\chi (G)$ .

4. Après avoir classé les sommets de  $G$  par ordre de degré décroissant, colorier le graphe  $G$ .

5. Combien de parties l'organisateur du concert doit-il prévoir ? Proposer une répartition des musiciens pour chacune de ces parties. 

Solution

1. La matrice d'adjacence de ce graphe est  $A=\left(\begin{array}{ccccccc}0& 0& 0& 1& 1& 1& 1\\ 0& 0& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 1& 1\\ 1& 0& 0& 0& 0& 1& 0\\ 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1& 1& 0\end{array}\right)$

2. a.  $G^{\prime }=K_4$  est le graphe simple complet d'ordre $4$ .
    b. Le nombre chromatique de  $G^{\prime }$  est donc  $\chi (G^{\prime })=4$ .
    c. Comme  $G^{\prime }$  est un sous-graphe de  $G$ , le nombre chromatique de  $G$  est  $\chi (G)\ge \chi (G^{\prime })$  donc  $\chi (G)\ge 4$

3. Le sommet de plus haut degré de  $G$  est F, qui est de degré 6, donc  $\chi (G)⩽7$ .
On a donc  $4⩽\chi (G)⩽7$

4. Voici les degrés des différents sommets :

$\begin{array}{|cccccccc|}\hline \text{Sommet}& \text{F}& \text{E}& \text{A}& \text{G}& \text{C}& \text{B}& \text{D}\\ \text{Degré}& 6& 5& 4& 4& 4& 3& 2\\ \hline\end{array}$

On va commencer par colorier le sous graphe  $G^{\prime }$ (AEFG) avec une couleur par sommet, puis on s'intéresse à C puis B et enfin D.

Remarque : pour B et C, on n'a pas le choix de la couleur, mais D pourrait être de la couleur de B et G ou de la couleur de E. La solution n'est pas unique.
Le nombre chromatique de  $G$  est finalement  $\chi (G)=4$

5. L'organisateur doit prévoir 4 parties.

Proposition n° 1 : 

$\begin{array}{|ccccc|}\hline \text{Partie}& n°1& n°2& n°3& n°4\\ \text{Musiciens}& \text{A}\text{C}& \text{B}\text{D}\text{G}& \text{E}& \text{F}\\ \hline\end{array}$

Proposition n° 2 :

$\begin{array}{|ccccc|}\hline \text{Partie}& n°1& n°2& n°3& n°4\\ \text{Musiciens}& \text{A}\text{C}& \text{B}\text{G}& \text{D}\text{E}& \text{F}\\ \hline\end{array}$